1. Field of the Invention
The present invention relates generally to an improved data processing system. More specifically, the present invention is directed to a computer implemented method, apparatus, and computer useable program code to prevent livelock created by competing updates of event outcome prediction information.
2. Description of the Related Art
Computer processors and other data processing systems sometimes find that event outcome prediction expedites the processing of data. Later, if the event outcome prediction is proven to be incorrect, these systems recover from the mispredictions. Then, these systems use the actual event outcome to update a prediction mechanism, such as a history-based hardware predictor table, in order to have a better chance of making correct event outcome predictions in the future.
However, this approach to event outcome prediction correction may lead to “livelock” in some prediction systems. Livelock is an endless loop in program execution that occurs when a process repeats itself because the process continues to receive erroneous information. For example, one event, or set of events, identified as A, serves to counter-act the forward progress of another event, or set of events, identified as B. Likewise, B serves to counter-act the forward progress of A.
Assume that events A and B only make forward progress if they receive a successful event outcome prediction from the prediction mechanism. Furthermore, assume an erroneous event outcome prediction puts in motion a sequence of actions that updates the prediction mechanism so that the next time the system executes the event, the event receives a correct prediction and is able to proceed forward. Using the two assumptions above in an example, the system executes event A, which receives an erroneous event outcome prediction from the prediction mechanism and then the system executes event B, which also receives an erroneous event outcome prediction. In this situation where both events A and B receive an erroneous event outcome prediction, it is possible for the system to update the prediction mechanism for event B prior to the system re-executing event A. The updates to the prediction mechanism for event B may serve to overwrite, or undo, the updates to the prediction mechanism for event A.
Consequently, when the system tries to re-execute event A, event A once again receives a wrong event outcome prediction. This second wrong event outcome prediction for event A occurs because after the system updated the prediction mechanism for event A, and before the system re-executes event A, the system updates the prediction mechanism for event B destroying event A's updates. Then, the updates to the prediction mechanism for the re-execution of event A destroy the updates to the prediction mechanism for the re-execution of event B.
As a result, event B also receives a wrong event outcome prediction when the system re-executes event B. Thus, any forward progress in the system for events A and B comes to a standstill because of the resultant livelock. This livelock situation may continue forever or until a user stops the system due to frustration with the lack of forward progress.
One known solution to livelock is exponential back-off. Exponential back-off is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. Exponential back-off is often used in network congestion avoidance to help determine the correct sending rate. In a livelock situation, upon incurring an event outcome misprediction, the event waits a random amount of time before trying again. If the event fails a second time, the event waits a longer random amount of time. If the event fails a third time, the event waits an even longer random amount of time and so on.
As these exponential back-offs continue, the probability that two conflicting events will keep conflicting rapidly drops toward zero. Therefore, this exponential back-off mechanism serves to disentangle two conflicting events. However, in a computer processor this exponential back-off solution is impractical for at least two reasons. First, no simple mechanism currently exists to calculate the random back-offs required for the event. Second, processor performance may significantly degrade due to increasing time intervals between event execution.
A second known solution to this livelock problem is to use a livelock detection counter. The livelock detection counter detects when an event is repeatedly executing. After the livelock detection counter reaches a predetermined threshold for execution of the event, the livelock detection counter assumes that livelock exists within the system, even if there is not, because it may be impossible to know for sure whether livelock actually exists. When the livelock detection counter assumes that there is livelock, the system executes one event at a time in a very simple mode until the system is reasonably confident that the livelocking events have passed. Like the previous approach above, this approach may significantly degrade computer processor performance due to slowing execution of events to one-at-a-time until livelock no longer exists within the system.
A variation to the second approach above is to introduce pipeline stalls, or bubbles, in the system when livelock is determined. Thus, when the first event re-executes after a livelock condition has been detected, the first event does not wait for an event outcome prediction, but delays execution until the correct value is computed. Here again, accurately detecting a livelock situation is expensive.
A more sophisticated version of the second approach above may be to actually identify the conflicting events causing livelock and delay execution of one of the events until the other event has completed. This approach still may degrade computer processor performance, although probably not as much as with the previously mentioned approaches. However, this approach is more expensive in terms of memory area and processor cycles used for implementation. Also, it is more difficult to validate that this approach works in all cases.
A variation of the immediately preceding approach is to lock an event outcome prediction after updating the prediction mechanism for the first executing event of a livelocking pair of events. Thus, the next time the first event executes, the first event receives the correct value and is no longer in a livelock condition with the second event. Accurately detecting this livelock condition is a problem as with the other approaches. In addition, locking event outcome predictions may create a problem if a third event executes and interrupts the normal event execution flow within the system. Any such third event must then check for locked event outcome predictions and release them.
Another known approach is to assign random event outcome predictions for a brief period when apparent livelock is detected. If the set of possible values for the event outcome prediction is small, this approach is likely to let one or both conflicting events pass, thus, resolving the livelock condition. However, using this approach may once again degrade computer processor performance during the period of assigning random event outcome predictions.
Therefore, it would be beneficial to have an improved computer implemented method, system, and computer useable program code to prevent livelock created by competing updates of event outcome prediction information.